package com.leecode;

import java.util.*;
import java.util.function.BiConsumer;

/**
 * 23. 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 */
public class Leet23 {
	public static void main(String[] args) {
		ListNode[] listNodes = new ListNode[2];
//		listNodes[0] = new ListNode(1, new ListNode(4, new ListNode(5)));
//		listNodes[1] = new ListNode(1, new ListNode(3, new ListNode(4)));
//		listNodes[2] = new ListNode(2, new ListNode(6));
//		new Leet23().mergeKLists(listNodes);


		listNodes[0] = new ListNode(1, new ListNode(2));
		listNodes[1] = new ListNode(3, new ListNode(4));
		new Leet23().mergeKLists2(listNodes);

	}

	/**
	 * 30%,97%,自创
	 */
	public ListNode mergeKLists(ListNode[] lists) {
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		for (ListNode listNode : lists) {
			while (listNode != null) {
				if (!map.containsKey(listNode.val)) {
					map.put(listNode.val, 1);
				} else {
					map.put(listNode.val, map.get(listNode.val) + 1);
				}

				listNode=listNode.next;//bug:没有移动ref
			}
		}

		ListNode dummy = new ListNode();
		ListNode res=dummy;
		if (map.isEmpty()) return null;//bug:return dummy,leet这边界是有毒!!
		for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
			for (int a = 0; a < integerIntegerEntry.getValue(); a++) {
				dummy.next = new ListNode(integerIntegerEntry.getKey());
				dummy=dummy.next;//bug:没有移动ref
			}
		}

		return res.next;
	}

	public ListNode mergeKLists2(ListNode[] lists) {
		if (lists == null || lists.length == 0) return null;
		PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
			@Override
			public int compare(ListNode o1, ListNode o2) {
				if (o1.val < o2.val) return -1;
				else if (o1.val == o2.val) return 0;
				else return 1;
			}
		});
		ListNode dummy = new ListNode(0);
		ListNode p = dummy;
		for (ListNode node : lists) {
			if (node != null) queue.add(node);
		}
		while (!queue.isEmpty()) {
			p.next = queue.poll();//弹出
			p = p.next;
			if (p.next != null) queue.add(p.next);//12,34-->2,34,证明add的时候也是会按照comparator的
		}
		return dummy.next;
	}

}
